#include <iostream>
using namespace std;

int match(char* reg, char* txt);
int match_here(char* reg, char* txt);
int match_star(int c, char* reg, char* txt);

int match(char* reg, char* txt) {
	if (reg[0] == '^')
		return match_here(reg+1, txt);
	
	do {
		if (match_here(reg, txt))
			return 1;
	} while (*txt++ != '\0');
	
	return 0;
}

int match_here(char* reg, char* txt) {
	if (reg[0] == '\0')
		return 1;
	if (reg[1] == '*')
		return match_star(reg[0], reg+2, txt);
	if (reg[0] == '$' && reg[1] == '\0')
		return *txt == '\0';
	if (*txt!='\0' && (reg[0]=='.' || reg[0]==*txt))
		return match_here(reg+1, txt+1);
		
	return 0;
}

int match_star(int c, char* reg, char* txt) {
	do {
		if (match_here(reg, txt))
			return 1;
	} while (*txt!='\0' && (*txt++==c || c=='.'));
	
	return 0;
}

int main() {
	char str[] = "tommababcabc";
	char key[] = "t.m*ab*abc";
	cout<<match(key, str)<<endl;
	
	return 0;
}